package pers.qianyu.month_202101.date_20210123;

/**
 * 1319. 连通网络的操作次数
 * https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/
 *
 * @author mizzle rain
 * @date 2021-01-23 19:44
 */
public class MakeConnected {
    int[] p;

    int find(int x) {
        while (p[x] != x) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }

    public int makeConnected(int n, int[][] connections) {
        int len = connections.length;
        p = new int[n];
        for (int i = 0; i < n; i++) p[i] = i;
        int count = n;
        for (int[] c : connections) {
            if (find(c[0]) != find(c[1])) {
                p[find(c[0])] = p[find(c[1])];
                count--;
            }
        }
        if (count == 1) return 0;
        return len >= n - 1 ? count - 1 : -1;
    }
}
